#!/usr/bin/env python
#coding=utf-8

import numpy as np
from numpy import array
import json
from circleCover import generateFirstLevelNodes
from circleUtils import radius, points, edges, areas, getPointThroughput
from pprint import pprint
import math
import sys
from heapq import *


    
def updateFlowMat(circle_cover):
    """
    计算每两个一级节点之间的流量矩阵
    """
    circles = sorted([x[0] for x in circle_cover])
    mat = [ [calcFlow(circle_cover[i],circle_cover[j])  
            for j in range(len(circles))] 
            for i in range(len(circles)) ]


    # 将物流园区节点也添加入流量矩阵
    for i in range(len(mat)):
        l = mat[i]
        for j in range(4):
            l.append(calcFlow(circle_cover[i], j))

    for i in range(4):
        l = []
        l.extend([calcFlow(i, circle_cover[j]) for j in range(len(circles))])
        l.extend([0,0,0,0])
        mat.append(l)
    return mat

def calcFlow(c_from ,c_to):
    """
    计算两个一级节点之间（或物流园区与一级节点之间）的货运流量总和
    """
    if type(c_from) is int and type(c_to) is int:
        return 0
    if type(c_from) is int:
        return sum(edges[c_from][y] for y in c_to[1])
    if type(c_to) is int:
        return sum(edges[x][c_to] for x in c_from[1])
    if c_from[0]==c_to[0]:
        return 0
    return sum(edges[x][y]  for x in c_from[1] for y in c_to[1])

def distance(a, b):
    """
    两个二维平面点之间的欧几里得距离
    """
    x = array(a)
    y = array(b)
    assert x.shape == (2,)
    assert y.shape == (2,)

    return np.linalg.norm(x-y)


    


def generateSecondLevelNode(optimize=False):
    """
    根据一级节点以及流量矩阵，生成所有二级矩阵
    """
    # 覆盖圆的坐标
    # 经过孤立点优化的数据
    # circles = [(149249.15514157506, 151724.94949693873), (156440.16440270093, 162220.4203392166), (150413.22, 159364.66), (145146.77, 151489.56), (141612.02, 152424.78), (147318.00681410765, 157756.9752697945), (163428.02, 166293.35), (140559.50462796353, 153925.49084725173), (138198.68971013036, 157637.74073388154), (142557.84711897696, 158192.3551838773)]
    # 未经孤立点优化的数据
    # circles = [[140559.50462796353, 153925.49084725173], [147318.00681410765, 157756.9752697945], [145146.77, 151489.56], [156440.16440270093, 162220.4203392166], [142557.84711897696, 158192.3551838773], [149249.15514157506, 151724.94949693873], [138198.68971013036, 157637.74073388154], [163428.02, 166293.35], [150413.22, 159364.66], [141612.02, 152424.78], [157354.7, 166956.66], [169251.06, 165333.16], [146444.34, 161044.58]]
    circles = generateFirstLevelNodes(optimize)

    # 后续所有表格的输出都以排过序的circle为准
    circles = sorted(circles)

    index_points = zip(range(4, len(points)),points[4:])

    circle_cover = []
    for c in circles:
        circle_cover.append( (c, set([x[0] for x in index_points if distance(c, x[1])<=radius+1e-3])) )

    
    # 对于每个区域中心，选择一个离它最近的节点，在其它节点的区域集合里删去
    for x in range(4, len(points)):
        c = [t[0] for t in circle_cover if x in t[1]] # 包含x的节点集合
        if not c:
            continue
        s = min(c, key=lambda t:distance(array(t), points[x])) # 目标最近节点
        for k in circle_cover:
            if k[0]!=s:
                ppp = k[1]
                ppp -= set([x])

    mat = updateFlowMat(circle_cover)
    mat = array(mat)

    
    
    # 节点分配优化：重分配区域中心与一级节点的所属关系，尽量使得每个一级节点的吞吐量之和接近4000+3000*n，以让二级节点尽量满载
    if optimize:
        # for i,(c,s) in enumerate(circle_cover):
        #     throughput = mat[i].sum() + mat.transpose()[i].sum()
        #     remain = (throughput - 4000) % 3000
        #     print i,remain
        
        changed = True

        threshold = 1500
        # 记录所有已经抛出过的一级节点，不会向它们转移
        thrown_out = []
        # 枚举节点，计算其吞吐量是否合适，否则枚举包含的每一个区域中心点尝试转移

        
        while changed:
            changed = False

            # 每次重新分配，mat都会改变
            # 每次从重新计算的吞吐量里面选择一个最小的开始操作
            fln_throughput = [ (k, mat[k].sum() + mat.transpose()[k].sum()) for k,_ in enumerate(circles)]
            fln_throughput = sorted(fln_throughput, key=lambda x:x[1])

            # 如果没有发生重分配，那就继续从小到大寻找可能的操作节点
            for i, throughput in fln_throughput:
                remain = (throughput - 4000) % 3000
                # if remain>=threshold:
                #     break
                # 尝试甩一个区域中心点到别的地方去
                point_set = set(circle_cover[i][1])
                for centerPoint in point_set:
                    pt = points[centerPoint]
                    point_tp = getPointThroughput(centerPoint)
                    if (remain - point_tp) % 3000< threshold:
                        break
                    sati_fln = []
                    for k, fln in enumerate(circles):
                        if k!=i and k not in thrown_out and distance(fln, pt)<=radius+1e-3:
                            sati_fln.append((k, fln))
                    # if i == 11:
                    #     print circle_cover[i]
                    #     print sati_fln
                    for k,fln in sati_fln:
                        if k==i:
                            continue
                        # print k, fln[0]
                        fln_throughput = mat[k].sum() + mat.transpose()[k].sum()
                        fln_remain = (fln_throughput - 4000) % 3000
                        if (point_tp + fln_remain) % 3000 >=threshold :
                            circle_cover[i][1].remove(centerPoint)
                            circle_cover[k][1].add(centerPoint)
                            changed = True
                            thrown_out.append(i)
                            # print "Transfer {} from {} to {}".format(point_tp, i, k)
                            # 转移已经完成，重新计算mat和节点的吞吐量
                            mat = array(updateFlowMat(circle_cover))
                            throughput = mat[i].sum() + mat.transpose()[i].sum()
                            remain = (throughput - 4000) % 3000
                            # 不再查找下一个用于分配的节点
                            break
                    if changed:
                        # 如果重分配已经发生，则不再尝试下一个区域中心点
                        break

        # for i,(c,s) in enumerate(circle_cover):
        #     throughput = mat[i].sum() + mat.transpose()[i].sum()
        #     remain = (throughput - 4000) % 3000
        #     print i,remain           
                
    
    # 计算一个一级节点周围需要几个二级节点
    mat = array(mat)
    second_level_node_number = []
    circle_cover_dict = {tuple(x[0]):x[1] for x in circle_cover }

    # 计算一个二级节点的总列表
    # 包含每个二级节点的：自身坐标，所属一级节点编号，所管理的区域编号list，所处理的吞吐量
    second_level_node_list = []
    throughput_list = [ ]

    for i in range(len(circles)):
        throughput = mat[i].sum() + mat.transpose()[i].sum()
        throughput_list.append(throughput)
        number = int(math.ceil((float(throughput) -4000)/3000.0))
        # 将吞吐量较大(超过一个二级节点处理范围)的点取出独立处理
        tuple_points = [tuple(x) for x in points]
        big_points = [ x for k, x in enumerate(tuple_points) 
            if k in circle_cover[i][1] and  getPointThroughput(k)>3000]
        for p in big_points:
            point_index = tuple_points.index(p)
            # 假设其面积为圆，若算出的半径r和其与一级节点的距离相加小于R，则不考虑
            area = areas[point_index]
            r = math.sqrt(area / math.pi) * 1000
            if r + distance(p, circles[i]) < radius:
                continue

            # 否则在上面单独设立足以覆盖其吞吐量数量的二级节点
            tp = getPointThroughput(point_index)
            sln_number = int(math.ceil(tp / 3000.0))
            ave_out = edges.transpose()[point_index].sum() / sln_number
            # print "ave_out:", ave_out
            for kkk in range(sln_number):
                second_level_node_list.append( (p, i, [point_index], ave_out))


        second_level_node_number.append(number)
        second_level_node_list.extend( (circles[i], i,() , 0) for k in range(number) )

    second_level_node_number = [x if x>0 else 0 for x in second_level_node_number ]
    

    # 如果进行了孤立点优化，需要额外的操作
    # 找出所有孤立点
    # 对每个孤立点，找出离其最近的一级节点，在如图位置修建足够数量的二级节点
    # 修建二级节点的数量由该区域中心点的吞吐量决定
    # 将该区域中心点加入对应一级节点
    # 更新一级节点的流量矩阵
    # 一级节点-----------二级节点--------3公里---------孤立点
    if optimize:
        tuple_points = [tuple(p) for p in points]
        isolate_points = []
        for p in tuple_points[4:]:
            if not any(c for c in circle_cover if tuple_points.index(p) in c[1]):
                isolate_points.append(p)
        
        for p in isolate_points:
            point_index = tuple_points.index(p)
            # abbr for First Level Node
            fln = min(circles, key=lambda c: distance(c, p))

            fln_index = circles.index(fln)
            x, y = fln
            a, b = p
            d = distance(fln, p)
            # (u-a) / (x-a) = radius /d
            # (v-b) / (y-b) = radius /d
            u = (x-a) * (radius/d) + a
            v = (y-b) * (radius/d) + b

            # 根据区域中心点的吞吐量计算所需二级节点数量
            throughput = edges[point_index].sum() + edges.transpose()[point_index].sum()
            number = int(math.ceil((float(throughput))/3000.0))

            # 将该区域中心点加入对应一级节点
            circle_cover[fln_index][1].add(point_index)

            # 将所有二级节点加入总表
            second_level_node_list.extend( 
                    ((u,v), fln_index, [point_index] , edges.transpose()[point_index].sum() / number) 
                    for i in range(number)
            )


        mat = updateFlowMat(circle_cover)
    
    # pprint(second_level_node_list)

    # # 二级节点平均分配优化
    # # 
    # if optimize:
    # print repr(circles)

    # 备用信息输出代码
    # print len(points)
    with open("out.temp", "w") as f:
        ddd = {
            "fln": circles,
            "mat": mat,
            "fln2pt": [list(x[1]) for x in circle_cover],
            "edges": edges.tolist(),
            "sln": second_level_node_list
        }
        json.dump(ddd, f)


    # print len(set.union(* [c[1] for c in circle_cover]))
    with open("节点信息.csv", "w") as f:
        # 对于各每个一级节点，输出其编号、坐标、管理的区域列表
        for index, c in enumerate(circle_cover):
            f.write("{},\"{}\",{}, {}\n".format(str(index), str(c[0]), ' '.join(str(t-4+791) for t in c[1]),0))
        f.write("\n\n\n\n")
        # 对于每个二级节点，输出其所属一级节点、坐标，管理的区域列表
        for c in second_level_node_list:
            f.write(
                "{},\"{}\",{}, {}\n".format( str(c[1]), str(c[0]), ' '.join(str(t-4+791) for t in c[2]),c[3])
            )
    return second_level_node_list

if __name__=="__main__":
    l = generateSecondLevelNode(True)
    print len(l)
    



